import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/21 18:52
 * @description Floyd算法，适用于任何图，且不管有向无向，边权正负。但是最短路必须存在
 * 时间复杂度为O(n^3)，适用于稠密图，即 m(边的数量)  约等于 n^2 (点的数量）
 */
public class Solution {
    /**
     * 邻接矩阵存储
     */
    int[][] graph;

    int INF = Integer.MAX_VALUE / 2;
    /**
     * 多源最短路算法
     * @param n n个结点 编号 0 - n-1
     * @param edges 边 e[0] - e[1] 的权值为 e[2]
     */
    public void floyd(int n, int[][] edges) {
        // 1. 初始化邻接矩阵
        graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            // 点到其他点的距离为无穷大
            Arrays.fill(graph[i], INF);
            // 点到自身的距离为0
            graph[i][i] = 0;
        }
        // 注意有向图和无向图的区别，无向图 u -> v，v -> u 都要设置，有向图 只要设置 u -> v
        for(int[] e: edges) {
            graph[e[0]][e[1]] = e[2];
            graph[e[1]][e[0]] = e[2];
        }
        // floyd 基本流程为三层循环：
        // 枚举中转点 - 枚举起点 - 枚举终点 - 松弛操作
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }
}
